
//1802.有界数组中指定下标处的最大值
class Solution {

    bool check(int n,int index,long long maxSum,long long t)
    {
        long long l=index,r=n-index-1;
        long long all=0;
        if(t>l) all+=t*(t-1)/2-(t-l-1)*(t-l)/2;
        else all+=t*(t-1)/2+l-t+1;
        if(t>r) all+=t*(t-1)/2-(t-r-1)*(t-r)/2;
        else all+=t*(t-1)/2+r-t+1;

        return all+t<=maxSum;
    }

public:
    int maxValue(int n, int index, int maxSum) {
        //直接进行模拟难度太大，如果已知最大值进行验证就比较简单了
        int left=0,right=maxSum+1;
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(n,index,maxSum,mid)) left=mid;
            else right=mid;
        }
        return left;
    }
};